package code.oldCode.binarySearch;

/**
 * @author cuihaoran
 * @date 2024/9/23
 */
public class BinarySearchQues {

    /**
     * 33. 搜索旋转排序数组
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid = 0;
        while (low <= high) {
            // 找到则结束
            mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[low] 的关系判断 mid 是在左段还是右段
            // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 low 和 high

            // 左半边正常（能这样判断的原因是nums中的值各不相同，81题就不能这么玩）
            if (nums[mid] >= nums[low]) {
                // 如果目标在左面
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                }
                // 如果目标在右面
                else {
                    low = mid + 1;
                }
            }
            // 左面不正常，右半边一定正常
            else {
                // 如果目标在右面
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                }
                // 如果目标在左面
                else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 81. 搜索旋转排序数组 II
     *
     * @param nums
     * @param target
     * @return
     */
    public boolean search2(int[] nums, int target) {
        // 比起33题，需要注意 nums = [1,0,1,1,1] 的情况
        int low = 0, high = nums.length - 1, mid = 0;
        while (low <= high) {
            mid = low + (high - low) / 2;
            // 找到直接结束
            if (nums[mid] == target)
                return true;
            // 与33题不同的地方，由于元素可以相同，故low、mid、high可能都一样，把这个去掉就是33题答案
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                low++;
                high--;
            }
            // 左面正常
            else if (nums[mid] >= nums[low]) {
                if (target >= nums[low] && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            // 如果右面是正常的
            else {
                if (target > nums[mid] && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }

        return false;
    }

    /**
     * 153. 寻找旋转排序数组中的最小值
     *
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        // 元素互不相同 {3 4 5 1 2} {5 1 2 3 4}
        int low = 0, high = nums.length - 1, mid = 0;
        int ans = Integer.MAX_VALUE;
        while (low <= high) {
            mid = low + (high - low) / 2;
            // 如果左半是正常的，那么要么是nums[low]，要么在右半
            if (nums[mid] >= nums[low]) {
                ans = Math.min(ans, nums[low]);
                low = mid + 1;
            }
            // 如果左半不正常，那么要么是nums[mid]，要么在左半
            else {
                ans = Math.min(ans, nums[mid]);
                high = mid - 1;
            }
        }

        return ans;
    }

    /**
     * 154. 寻找旋转排序数组中的最小值 II
     *
     * @param nums
     * @return
     */
    public int findMin2(int[] nums) {
        // 元素互不相同 {3 4 5 1 2} {5 1 2 3 4}
        int low = 0, high = nums.length - 1, mid = 0;
        int ans = Integer.MAX_VALUE;
        while (low <= high) {
            mid = low + (high - low) / 2;
            // 因为可以重复，所以有这个特殊情况，去掉这个if就是153题的答案
            if (nums[low] == nums[mid] && nums[mid] == nums[high]) {
                ans = Math.min(ans, nums[mid]);
                low ++;
                high --;
            }
            // 如果左半是正常的，那么要么是nums[low]，要么在右半
            else if (nums[mid] >= nums[low]) {
                ans = Math.min(ans, nums[low]);
                low = mid + 1;
            }
            // 如果左半不正常，那么要么是nums[mid]，要么在左半
            else {
                ans = Math.min(ans, nums[mid]);
                high = mid - 1;
            }
        }

        return ans;
    }

    /**
     * 34. 在排序数组中查找元素的第一个和最后一个位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid = 0;
        int begin = -1, end = -1;
        // 先找最左面
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else {
                begin = mid;
                right = mid - 1;
            }
        }
        // 再找最右面
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else {
                end = mid;
                left = mid + 1;
            }
        }

        return new int[]{begin, end};
    }

    /**
     * 35. 搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int ans = nums.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 当target<=nums[mid]时，将其插入左侧，不要ans变量直接返回left也行
            if (target <= nums[mid]) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 69. x 的平方根
     *
     * @param x
     * @return
     */
    public int mySqrt(int x) {
        int left = 0, right = x;
        int mid, ans = -1;
        while (left <= right) {
            mid = left + (right - left) / 2;
            // 因为mid*mid<=x时，mid是潜在答案，所以此时赋值ans=mid，并改变left寻找更大的可能的答案
            if ((long) mid * mid <= x) {
                left = mid + 1;
                ans = mid;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 74. 搜索二维矩阵
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int arrayLeft = 0;
        int arrayRight = matrix.length - 1;
        boolean ans = false;
        while (arrayLeft <= arrayRight) {
            int arrayMid = arrayLeft + (arrayRight - arrayLeft) / 2;
            int left_mid = 0, right_mid = matrix[arrayMid].length - 1;
            // target在中间的数组里，在这个数组里进行二分查找
            if (target >= matrix[arrayMid][left_mid] && target <= matrix[arrayMid][right_mid]) {
                int left = 0, right = matrix[arrayMid].length - 1;
                while (left <= right) {
                    int mid = left + (right - left) / 2;
                    if (matrix[arrayMid][mid] == target) {
                        return true;
                    } else if (matrix[arrayMid][mid] > target) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                return false;
            }
            // target在mid上面的数组中
            else if (target < matrix[arrayMid][left_mid]) {
                arrayRight = arrayMid - 1;
            }
            // target在mid下面的数组中
            else {
                arrayLeft = arrayMid + 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        BinarySearchQues binarySearchQues = new BinarySearchQues();
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        System.out.println(binarySearchQues.findMin(new int[]{3, 4, 5, 1, 2}));
    }
}
